package stack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class StackOJ {
    //最小栈
    class MinStack {
        Stack<Integer> minstack = new Stack<>();
        Stack<Integer> stack = new Stack<>();
        public MinStack() {

        }

        public void push(int val) {
            stack.push(val);
            if (minstack.isEmpty()) {
                minstack.push(val);
                return;
            }
            if (val < minstack.peek()) {
                minstack.push(val);
            }else {
                minstack.push(minstack.peek());
            }
        }

        public void pop() {
            stack.pop();
            minstack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minstack.peek();
        }
    }

    //括号匹配问题
    public boolean isValid(String s) {
        if (s == "") {
            return true;
        }
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i < arr.length;i++) {
            if (arr[i] == ')') {
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                    continue;
                }else {
                    return false;
                }
            }
            if (arr[i] == ']') {
                if (!stack.isEmpty() && stack.peek() == '[') {
                    stack.pop();
                    continue;
                }else {
                    return false;
                }
            }
            if (arr[i] == '}') {
                if (!stack.isEmpty() && stack.peek() == '{') {
                    stack.pop();
                    continue;
                }else {
                    return false;
                }
            }
            stack.push(arr[i]);
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }

    //栈的弹出压入序列
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0;i < pushV.length;i++) {
            stack.push(pushV[i]);
            while (!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length) {
                stack.pop();
                j++;
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }

    //逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        if (tokens.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0;i < tokens.length;i++) {
            if (!stack.isEmpty() && tokens[i].equals("+")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a + b);
                continue;
            }
            if (!stack.isEmpty() && tokens[i].equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
                continue;
            }
            if (!stack.isEmpty() && tokens[i].equals("*")) {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a * b);
                continue;
            }
            if (!stack.isEmpty() && tokens[i].equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
                continue;
            }
            stack.push(Integer.parseInt(tokens[i]));
        }
        return stack.pop();
    }

    //设计循环队列
    class MyCircularQueue {
        int head = 0;
        int tail = 0;
        int size = 0;
        int[] queue = new int[1000];
        public MyCircularQueue(int k) {
            int[] queue2 = new int[k];
            for (int i = 0;i < k;i++) {
                queue2[i] = queue[i];
            }
            queue = queue2;
        }

        public boolean enQueue(int value) {
            if (size == queue.length) {
                return false;
            }
            queue[tail] = value;
            tail++;
            if (tail == queue.length) {
                tail = 0;
            }
            size++;
            return true;
        }

        public boolean deQueue() {
            if (size == 0) {
                return false;
            }
            head++;
            if (head == queue.length) {
                head = 0;
            }
            size--;
            return true;
        }

        public int Front() {
            if (size == 0) {
                return -1;
            }
            return queue[head];
        }

        public int Rear() {
            if (size == 0) {
                return -1;
            }
            if (tail == 0) {
                return queue[queue.length - 1];
            }else {
                return queue[tail - 1];
            }
        }

        public boolean isEmpty() {
            if (size == 0) {
                return true;
            }
            return false;
        }

        public boolean isFull() {
            if (size == queue.length) {
                return true;
            }
            return false;
        }
    }

    //用栈实现队列
    class MyQueue {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        public MyQueue() {

        }

        public void push(int x) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            stack2.push(x);
            while (!stack2.empty()) {
                stack1.push(stack2.pop());
            }
        }

        public int pop() {
            return stack1.pop();
        }

        public int peek() {
            return stack1.peek();
        }

        public boolean empty() {
            return stack1.empty();
        }
    }

    //用队列实现栈
    class MyStack {
        Queue<Integer> queue1 = new LinkedList<>();

        public MyStack() {

        }

        public void push(int x) {
            Queue<Integer> queue2 = new LinkedList<>();
            queue2.offer(x);
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            queue1 = queue2;
        }

        public int pop() {
            return queue1.poll();
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            if (queue1.isEmpty()) {
                return true;
            }
            return false;
        }
    }
}
